#include <iostream>
#include "SortTestHelper.h"
#include "InsertSortionSort.h"

static int count = 0;

template<typename T>
//合并两个有序数组（采用额外的辅助空间进行合并）
void __merge(T arr[], int l, int mid, int r) {

    T aux[r - l + 1];
    for (int i = l; i <= r; i++) {
        aux[i - l] = arr[i];
    }


    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {

        if (i > mid) {
            arr[k] = aux[j - l];
            j++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i++;
        } else if (aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
            i++;
        } else {
            arr[k] = aux[j - l];
            j++;
            count += mid - l + 1;
        }
    }
}

//采用arr[l, r]，当排序数据量较小的时候采用插入排序提高效率
template<typename T>
void __mergeSortBeat(T arr[], int l, int r) {

    if (r - l < 15) {
        insertionSortBeat(arr, l, r);
        return;
    }

    int mid = l + (r - l) / 2;

    //递归划左右分子区间
    __mergeSortBeat(arr, l, mid);

    __mergeSortBeat(arr, mid + 1, r);

    //优化点：当要合并的数组前后无序的时候才进行合并，有序直接返回。减少合并次数，提高效率
    if (arr[mid] > arr[mid + 1]) {
        //合并
        __merge(arr, l, mid, r);
    }

}

/**
 * 归并排序,优化版
 * 当数据量比较小的时候采用插入排序
 *
 * @param arr
 * @param n
 */
template<typename T>
void mergeSortBeat(T arr[], int n) {

    __mergeSortBeat(arr, 0, n - 1);
}

int main() {

    int n = 10000;
    int * arr = SortTestHelper::generateRandomArray(n ,0,n);

    mergeSortBeat(arr,n);

    cout<<"逆序对为 ： "<<count<<endl;

    return 0;
}